package demo2;

import java.util.Stack;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    //寻找根节点到目标节点的路径
    private boolean getPath (TreeNode root, TreeNode p, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        if (root == p) {
            return true;
        }
        boolean left = getPath(root.left,p,stack);
        if (left) {
            return true;
        }
        boolean right = getPath(root.right,p,stack);
        if (right) {
            return true;
        } else {
            stack.pop();
            return false;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int sizeP = stack1.size();
        int sizeQ = stack2.size();
        Stack<TreeNode> cur = stack1;
        int size = sizeP - sizeQ;
        if (sizeP < sizeQ) {
            cur = stack2;
            size = -size;
        }
        while (size-- != 0) {
            cur.pop();
        }
        while (stack1.peek() != stack2.peek()) {
            stack1.pop();
            stack2.pop();
        }
        return stack1.peek();
    }

}